/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s: string): string[] {

    var isValid = (s: string) => {
        var count = 0;
        for(var c of s) {
            if (c === '(') count++;
            else if(c === ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count === 0;
    }

    var answer = new Array<string>()
    var visited = new Set<string>()
    var toVisit = new Array<string>()

    toVisit.unshift(s);

    while(toVisit.length > 0) {
        var x = toVisit.pop();
        visited.add(x);
        if (isValid(x)) {
            answer.push(x);
        }
        if (answer.length > 0) continue ;
        for(var i = 0; i <= x.length; i++) {
            if (x[i] == '(' || x[i] == ')') {
                let newStr = x.substring(0, i) + x.substring(i+1);
                if (toVisit.indexOf(newStr) == -1 && newStr !== "" && !visited.has(newStr)) {
                    toVisit.unshift(newStr);
                }
            }
        }
    }

    return answer;
    //return answer.length === 0 ? [""] : answer;
};


//console.assert( removeInvalidParentheses( "()())()").join('\t') === "()()()\t(())()")
console.assert( removeInvalidParentheses( "(").join('') === "")